package data_structure.leetcode;

import java.util.Arrays;

public class SolutionOffer40_2 {

    public int[] getLeastKNumbers(int []arr,int k){

        int []result= Arrays.copyOfRange (arr,0,k);
        for(int i=((result.length - 1-1)/2);i>=0;i--){
            siftDown(result,i,result.length);
        }
        for(int j=k;j<arr.length; j++){

            if(arr[j]<result[0]){
                result[0]=arr[j];
                siftDown(result, 0, result.length);
            }
        }
        return result;
    }

    private void siftDown(int []arr,int k,int length){

        while(k*2+1<length){
            int i=k*2+1;
            int j=i+1;

            if(j<length&&arr[j]>arr[i]){
                i=j;
            }
            if(arr[0]>arr[i])break;
            swap (arr,k,i);
            k=i;
        }
    }
    
    private void swap(int arr[],int left,int parent){
        int temp=arr[left];
        arr[left] = arr[parent];
        arr[parent]=temp;
    }

}
